#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "heap.h"


#define MAX 100

/* *********************************************************************
 * 			DECLARACION DE LOS TIPOS DE DATO
 * ********************************************************************/

struct heap_t{
	
	size_t cant;
	size_t max;
	void** vector;
	cmp_func_t comparar;
};

/* *********************************************************************
 * 				    IMPLEMENTACION
 * ********************************************************************/

heap_t *heap_crear(cmp_func_t comparar){
	
	/*pide memoriapara el heap*/
	heap_t* heap = malloc(sizeof(heap_t));
	if (!heap) return NULL;

	/*pide memoria para el vector del heap*/
	
	heap->vector = malloc (MAX*sizeof(void*));
	if(!heap->vector){
		free(heap);
		return NULL;
	}
	
	for(int I=0;I<MAX;I++){
		/*inicializa el vector*/
		heap->vector[I] = NULL;
	}
	/*inicializa el resto*/
	heap->cant = 0;
	heap->max = MAX;
	heap->comparar = comparar;

	return heap;
}


bool heap_destruir(heap_t *heap, void destruir_elemento(void *e)){
	
	/* destruye */
	if (destruir_elemento){
		for (int I=0 ; I<heap->cant ; I++)
			destruir_elemento(heap->vector[I]);
	}
	/*libera*/
	free(heap->vector);
	free(heap);
	
	return true;
}


size_t heap_cantidad(const heap_t *heap){
	
	/*devuelve la cantidad*/
	return heap->cant;
}


bool heap_esta_vacio(const heap_t *heap){
	
	/*indica si esta vacio*/
	return (heap->cant == 0);
}


vector_t* heap_convertir_a_vector(heap_t *heap){

	vector_t* vector = vector_crear(heap->cant);
	if (!vector)
		return NULL;

	int i = 0;

	while (!heap_esta_vacio(heap)){

		vector_guardar(vector,i,heap_desencolar(heap));

		i++;

	}

	return vector;

}


void swap(void** elem1, void** elem2){
	
	void* Aux = *elem1;
	*elem1 = *elem2;
	*elem2 = Aux;
	
}


bool heap_redimensionar(heap_t* heap, int nuevo_tam){
	
	/*pide mas memoria*/
	void** datos_nuevo = realloc(heap->vector, nuevo_tam*sizeof(void*));
	/*control de errores*/
	if (!datos_nuevo) return false;
    
	/*hace los cambios*/
	heap->vector = datos_nuevo;
	/* Pongo en NULL las nuevas posiciones */
	for (int i = heap->max ; i<nuevo_tam ; i++)
		heap->vector[i] = NULL;
	
	heap->max = nuevo_tam;
    
	return true;
}


void upheap(heap_t* heap, void* elem, cmp_func_t comparar){

	int pos = heap->cant;
	/*guarda el nuevo elemento en la ultima posicion*/
	heap->vector[pos] = elem;
	int pos_padre = (pos-1)/2;
	int K; 
	while (pos>0){
		/*compara con el padre*/

		K = comparar(heap->vector[pos],heap->vector[pos_padre]);
		if (K>0){
			/*si es mayor intercambia*/
			swap (&heap->vector[pos],&heap->vector[pos_padre]);
			pos = pos_padre;
			pos_padre = (pos-1)/2;
		}else{
			return;
		}
	}
}


bool heap_encolar(heap_t *heap, void *elem){
	
	if (heap->cant == heap->max)/*redimensiona si esta lleno*/
		if(!heap_redimensionar(heap,heap->cant*2)) return false;
	/*inserta donde debe*/
	upheap(heap,elem,heap->comparar);
	/*aumenta la cantidad*/
	heap->cant++;
	/*devuelve*/
	return true;
}



void *heap_ver_max(const heap_t *heap){
	
	if (heap_esta_vacio(heap))
		return NULL;
	/*devuelve el primero*/
	return heap->vector[0];
}


void downheap (void** vector,int inicio,int fin,cmp_func_t cmp){

	if (inicio >= fin || inicio < 0)
		return;
		
	size_t h_izq = inicio*2 + 1;
	size_t h_der = inicio*2 + 2;
	
	if (h_izq >= fin)
		return;
	
	int K = cmp (vector[inicio],vector[h_izq]);
	int J = 0;
	
	if (h_der<fin)
		J = cmp (vector[inicio],vector[h_der]);
		
	if (K>=0 && J>=0)
		return;
		
	if (K<0 && J<0){
		K = cmp (vector[h_izq],vector[h_der]);
		
		if (K>0){
			swap (&vector[inicio],&vector[h_izq]);
			downheap (vector,h_izq,fin,cmp);
			return;
		}
		
		swap (&vector[inicio],&vector[h_der]);
		downheap (vector,h_der,fin,cmp);
		return;
	}
	
	if (K<0){
		swap (&vector[inicio],&vector[h_izq]);
		downheap (vector,h_izq,fin,cmp);
		return;
	}
	
		
	swap (&vector[inicio],&vector[h_der]);
	downheap(vector,h_der,fin,cmp);
	return;
}


void* heap_desencolar(heap_t *heap){
	
	if(heap->cant == 0) return NULL;
	
	/*aparto el primero*/
	void* dato = heap_ver_max(heap);
	/*aparto el ultimo*/
	void* dato2 = heap->vector[heap->cant-1];
	
	heap->vector[0] = dato2;
	
	/*saco el primero y reordeno*/
	downheap(heap->vector,0,heap->cant,heap->comparar);
	
	heap->cant--;
	heap->vector[heap->cant] = NULL;
	
	if ((heap->cant < heap->max/4) && (heap->cant > MAX)) 	
		heap_redimensionar(heap,(heap->max/2));
	
	/*devuelvo el 1º*/
	return dato;
}


void heapify (void** vector, int ini, int fin, cmp_func_t cmp){
	
	if (ini >= fin)
		return;
		
	for (int i = (fin + ini)/2 ; i >= ini ; i--){
		downheap (vector,i,fin,cmp); 
	}
	
}

void heapsort (void* elementos[], size_t fin, cmp_func_t cmp){
	
	heapify (elementos,0,fin,cmp);
	
	for (int i = fin-1 ; i > 0 ; i--){
		swap (&elementos[0],&elementos[i]);
		downheap(elementos,0,i,cmp);
	} 
	
}









